package recursion;

public class NoOfIsland200 {
    public static int numIslands(char[][] grid) {
        int isLandCnt = 0;
        int rowNum = grid.length;
        int colNum = grid[0].length;
        for (int i = 0; i < rowNum; i++) {
            for (int j = 0; j < colNum; j++) {
                boolean isIsland = false;
                isIsland = infect(grid, i, j, isIsland);
                if (isIsland)
                    isLandCnt++;
            }
        }
        return isLandCnt;
    }

    public static boolean infect(char[][] grid, int rowIdx, int colIndx, boolean isIsland) {

        if (rowIdx >= grid.length || colIndx >= grid[0].length ||rowIdx < 0|| colIndx < 0 || grid[rowIdx][colIndx] == '0')
            return isIsland;

        if (grid[rowIdx][colIndx] == '1') {
            grid[rowIdx][colIndx] = '0';
            isIsland = true;
        }

        infect(grid, rowIdx + 1, colIndx, isIsland);
        infect(grid, rowIdx, colIndx + 1, isIsland);
        infect(grid, rowIdx - 1, colIndx, isIsland);
        infect(grid, rowIdx, colIndx - 1, isIsland);
        return isIsland;
    }

    public static void main(String[] args) {
        char[][] grid = new char[][]{{'1', '1', '1'}, {'0', '1', '0'}, {'1', '1', '1'}};
        System.out.println(numIslands(grid));
    }
}
